补题进度：2/11
tls组合数学选讲
中山左老师训练题
组合数学选讲
A
题意
题解
B
题意
题解
C
题意
题解
D
题意
题解
E
题意
题解
F
题意
定义一颗二叉树的
高度差：二叉树所有节点左右儿子高度差的最大值
不平衡度：这棵树的所有节点左右子树节点数之差的最大值
问所有高度为n的二叉树中，高度差不超过d的树不平衡度的最大值
题解
高度为$n$的树的高度差最大为$d$
不平衡度的最大值一定是：一颗高度为$n-1$的满二叉树，和一颗高度为$n-1$最大不平衡二叉树，之差。
高度为n-1的满二叉树的节点数为$2^{n-1}-1$
高度为$n-1$的最大不平衡二叉树的节点数为$f(n)$
$$
f(n)=1+f(n-1)+f(n-d-1) (n>d)
$$
$$
f(n)=n (n<=d)
$$
G
题意
题解
H
题意
$n$ 张卡片，其中 $m$ 张是特殊卡片，每次可以去一张牌。问取出的至少有 $k$ 张特殊卡片的期望次数(特殊卡不放回)
题解
- 显然满足几何分布
- 这里的至少k张实际上就是恰好k张
- $\sum_{i=0}^{k-1} \frac {n-i}{m-i}$